/*
    题目描述：链接：https://leetcode.cn/problems/maximum-subarray/
    给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
    子数组 是数组中的一个连续部分。

    输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
    输出：6
    解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
*/

/*
    解题思路：动态规划
    1. 遍历数组元素，如果累计相加的大于这个元素，就说明可以加上去
    2. 小于就直接从这个元素开始相加
*/

function maxSubArray(nums) {
    if (!nums) return false;

    let dp = [nums[0]], res = nums[0];

    for (let i = 1; i < nums.length; i++) {
        dp.push(Math.max(nums[i], nums[i] + dp[dp.length - 1]));

        if (res < dp[dp.length - 1]) {
            res = dp[dp.length - 1];
        }
    };

    return res;
};


// test
const num = [-2,1,-3,4,-1,2,1,-5,4];
const res =  maxSubArray(num);

console.log(res);   // 6